/*
Implement int sqrt(int x).

Compute and return the square root of x.
*/

class Solution {
public:
    int sqrt(int x) {
        if (x < 2) return x;
        int low = 0, high = x;
        while (low <= high) {
            int mid = (low+high)/2;
            int quotient = x/mid;
            if (quotient == mid) {
                return mid;
            } else if (quotient > mid) low=mid+1;
            else high=mid-1;
        }
        return high;
    }
};

#if 0
class Solution {
public:
    int sqrt(int x) {
        if (!x) return 0;
        if (x == 1) return 1;
        int low = 0;
        int high = x;
        while (high - low > 1) {
            int midint = (low + high) / 2;
            double mid = (double)midint;
            double mul = mid * mid;
            int mulint = (int)mul;
            if (mul > (double)INT_MAX || mulint > x) {
                high = mid;
            } else if (mulint < x) {
                low = mid;
            } else {
                return mid;
            }
        }
        return low;
    }
};
#endif
